/*
提交链接：https://leetcode.cn/problems/longest-univalue-path/description/
提交题目：687.最长同值路径
提交时间：2024/10/10
*/

class Solution {
public:
    int ans = 0;                   // 表示结点个数
    int longestUnivaluePath(TreeNode* root) {
       if(root==NULL) return 0;
        dfs(root);
        return ans-1;               // ans-1表示路径长度   
 }

    int dfs(TreeNode* node)          // node往下走最远能走多远得到最长相同路径(无拐点，单一方向深入)
    {
        if(node==NULL) return 0;           // 该节点为空返回0
        int len1=dfs(node->left);         // 结点不为空，搜左边（从这个左节点最远走到多远）
        int len2=dfs(node->right);       // 结点不为空，搜右边（从这个右节点最远走到多远）
        int L=0,R=0;           // 用于更新符合题目要求的ans结点个数
        if(node->left&&node->left->val==node->val)   // 左节点存在并且等于该根节点的值（意味len1有用）
            L=len1;
        if(node->right&&node->right->val==node->val)   //右节点存在并且等于该根节点的值（意味len2有用）
            R=len2;
        ans=max(ans,L+R+1);    // ans记录的是节点，所以要在边的基础上+1
        return max(L,R)+1;     // 返回节点数
    }
};

